package com.github.yangyishe.p100;

public class Problem55S2 {
    public static void main(String[] args) {
        int[] nums=new int[]{3,2,1,0,4};

        Problem55S2 problem55S2 = new Problem55S2();
        boolean canJump = problem55S2.canJump(nums);
        System.out.println("canJump = " + canJump);
    }

    /**
     * 思路：
     * 数组相关的一半问题，都可用双指针解决，这道也不例外。
     * slow记录遍历的索引，fast记录索引上限。
     * 归根结底，这是一道非典型的快慢指针问题。典型的快慢指针是遍历快指针；这道则是遍历慢指针。
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums){
        if(nums.length==1){
            return true;
        }
        int slow=0,fast=0;

        while(slow<=fast){
            fast=Math.max(fast,slow+nums[slow]);
            if(fast>=nums.length-1){
                return true;
            }
            slow++;
        }

        return false;
    }
}
